Such a telephone network built for the purpose of intercommunication by voice as a public line of telephone communication, a leased line, and the like is restricted in transmission quality and transmission speed when being used in data communication. Therefore, public digital data networks more adaptive in such characteristics specific to data communication as data traffic characteristics and the like are being built up in various countries including Japan. The public digital data network uses transmission paths and switching systems for digital signals, and some services by circuit switching networks or packet switching networks are provided in Japan. For international connection also, international standardization is promoted by the International Telegraph and Telephone Consultative Committee (CCITT), and at present has been almost provided as recommendations (X-series Recommendations) related to such new data networks as circuit switching systems, packet switching systems, leased digital lines, and the like.
In recent years, a network called a Local Area Network (LAN) has been widely used for the purpose of sharing such information (data) as a database or the like and peripheral apparatuses. The LAN is a network for connecting digital apparatuses such as computers, communication terminals and the like distributed in such a limited specific area as an office, a factory, a laboratory, a university and the like, and has a kind of switching function. In such a LAN also, standardization of protocols and the like has been performed by Committee 802 of the Institute of Electrical and Electronic Engineers (IEEE), the International Standardization Organization (ISO) and the like.
The reference model for the Open Systems Interconnection (OSI) being applied to a public digital data network and the above-mentioned LAN protocol standardized by IEEE are defined by plural protocol layers which are defined as a physical layer to upper layers. Protocols used widely in Wide Area Networks (WAN) or other LANs and the like also are generally defined according to plural protocol layers. In such a way, most network protocols are defined according to plural protocol layers.
Plural networks such as LANs, WANs, public digital networks, or the like have been connected with one another up to now. For example, even networks which have at least a few protocol layers different from one another out of a plurality of protocol layers to define a protocol for a message to be transmitted have been connected with one another up to now.
Hereupon, an inter-network connecting device for connecting with each other through the second layer two networks which have the same Media Access Control (MAC) layer which is the second layer for OSI is called a bridge or the like. An inter-network connecting device for connecting to one another a plurality of networks which are different from one another in the first to seventh layers for OSI is called a gateway or the like. And an inter-network connecting device, as referred to as an embodiment described later in this application, for connecting to one another through the third layer a plurality of networks which are different from one another in the first to third layers for OSI is called a router or the like.
An inter-network connecting device which the present invention considers as an object is not limited to a router in an embodiment described later, but can be applied also to a bridge and a gateway described above for example. And also networks which an inter-network connecting device according to the present invention connects to one another are not limited to the above-mentioned specific LANS, but may be various LANs, WANs, public digital data networks.
Hereupon, an inter-network connecting device used up to now for connecting LANs to one another, particularly an Interment Protocol (IP) router is described in detail with regard to the present invention.
An IP router performs a process for determining a transmission path of a received frame (hereinafter referred to as an IP routing process) on the basis of the destination IP address in the IP header contained in the received frame. Such an IP routing process is performed as extracting various address components, particularly the network address of the destination IP address.
However, a general inter-network connecting device also performs a series of processes (called a routing process) for transferring a received message to an appropriate network at the destination side to be connected to the said inter-network connecting device as extracting various address components from the destination address in the received message and performing a control according to the various address components.
The destination IP address of 32 bits is composed of a total of three fields, namely, a class bit field, a network address bit field and a host address bit field, as shown in FIG. 1. Each of the fields is composed in this order from the most significant bit (MSB) side to the least significant bit (LSB) side of the IP address of 32 bits. As shown in FIG. 1, the number of bits of a network address bit field, the number of bits of a host address bit field as well as the number of bits of a class bit field are determined according to the address classes A to C indicated by the class bits.
As shown in FIG. 1, first, in case that the MSB of an IP address of 32 bits is "0", an address class of "A" (hereinafter referred to as class A) is shown in the class bit field. In this case the network address bit field becomes 7 bits and the host address bit field becomes 24 bits. In case that the first two bits from the MSB of an IP address are "10", an address class of "B" (referred to as class B) is shown in the class bit field. In this case the network address bit field becomes 14 bits and the host address bit field becomes 16 bits. And in the first three bits from the MSB of an IP address are "110", an address class of "C" (referred to as class C) is shown in the class bit field. In this case the network address bit field becomes 21 bits and the host address bit field becomes 8 bits.
Said network address indicates the address of a network on the Internet. The network address is represented with said class bits and said network address bits. A host address indicates the address of an individual host in a network indicated by said network addresses. The host address is represented with said host address bits.
Said IP router is disposed between plural networks and checks the destination IP address in the IP header contained in a received frame received from a network. The IP router checks particularly the network address in a destination IP address and when the IP network address is a network connected to a port of that IP router (its own port), the IP router extracts the MAC address from the host address of the IP address and transmits the frame to the corresponding host. On the other hand, in case that the network address in the IP address indicates an address other than a network to be connected to its own port, the IP router relays the received frame to another port.
When extracting a network address from an IP address of 32 bits, the IP router processes an IP address mask of a received frame. The mask process is performed by performing the AND operation of bits corresponding to each other between the IP address and a specified address mask. Here, an address mask is data of 32 bits like an IP address. Particularly, in an address mask for extracting a network address, bits at the same bit positions of the class bit and network address bit fields of an IP address are respectively "1", and the other bits at the same bit positions as the host address bit field of the IP address are "0".
Said address mask is used for extracting various address components such as a network address and the like by making the logical AND of it with such a destination address as an IP address or the like. Therefore, when a bit of an address mask is "1", the bit of a specific address component is extracted at that bit position, and hereinafter setting a bit as an object of extraction in such a way is expressed as "masking". On the other hand, when a bit of an address mask is "0", such a specific address component is not extracted, and setting a bit as non-object of extraction in such a way is expressed as "no masking (ignoring)".
If an IP address has one of only three classes A to C, a network address bit field also is one of only three fields, and accordingly it will do also to prepare only three kinds of address masks to be used in extracting network address bits. In case of actually extracting a network address, it will do to determine what class its address class is of classes A to C on the basis of the first one to three bits from the MSB of an IP address, select one of three kinds of address masks according to the determined class, and extract the corresponding network address bits by means of the selected address mask, and therefore it is possible to comparatively simply and automatically perform this network address extracting process.
In recent years, however, as the number of IP addresses becomes short, it is required to more effectively make good use of addresses to be represented by 32 bits. Thus, a multi-protocol process has been performed which uses the first several bits of a host address bits in addressing a subnetwork obtained by dividing a network into plural parts in consideration of treating said first several bits in the same way as network address bits.
In case that said IP router is provided between such multi-protocol subnetworks, it is necessary to perform a subnetwork address extracting process similar to said network address extracting process using an address mask and correctly relay a frame according to a subnetwork address extracted from the received frame. In order to extract a subnetwork address in such a manner, it is necessary to provide an address mask to be exclusively used.
Therefore, in order to cope with the network address or subnetwork address of a network to be connected, a recent IP router is provided with a table of not only IP addresses but also address masks corresponding to these IP addresses. Using such a table, the IP router extracts a network address or a subnetwork address in the IP address of a received frame. A method of using a table in such a manner is logically simple and easy to understand, but has a complicated problem as shown in the following in practical processing.
That is to say, in case that an IP address does not have a subnetwork address field, it is possible to determine an address class based on the first one to three bits from the MSB of the IP address contained in a received frame and obtain uniquely an address mask for extracting a network address. However, in case that an IP address has a subnetwork address field, it is not possible to obtain uniquely an address mask for extracting a subnetwork address or a network address. In an IP router, therefore, it is generally necessary to perform one of the following processes.
A1. A process of comparing with each other network addresses in a table contained in an IP router (network addresses obtained by mask-processing IP addresses in the table with address masks) and the IP address in a received frame, selecting an entry having the most number of bits coincident with the corresponding bits of the IP address among all entries in the table, and using the network address of the entry as the destination address.
A2. A process in which a masking process is performed treating as "1" all bits of an address mask corresponding to the IP address in a received frame and the result is compared with network addresses in the table; and in case that there is not a coincident address, the result obtained by setting the LSB as "0" is compared again with the network addresses in the table; and then in case that there is not a coincident address again, the result obtained by setting the bit next to the LSB also as "0" is compared again with the network addresses in the table; and in this manner, the results obtained by setting bit by bit the bits of the address mask as "0" from the LSB side are compared with the network addresses in the table until a coincident address is found.
As shown in the above-mentioned processes A1 and A2, in case of a multi-protocol process where there is a subnetwork field in an IP address, there has been up to now a problem that a process for extracting a network address becomes very complicated and the processing time becomes long. And such a process has a problem that it can be generally processed by only software and it is very difficult to form such a process into hardware. Moreover, to be provided with a table in which an address of 32 bits can be retrieved as it is even after extracting a network address is uneconomical due to increasing the number of data in the table. Accordingly, a fact that a special logical circuit needs to be provided at the outside and such a measure as a hash method of retrieving data in a tree-like form by means of a hash function is required results in imposing a great load on software.
Thus a high-performance central processing unit (CPU) is generally used in order to shorten the processing time. Even if a high-performance CPU is used, however, shortening of the processing time is limited and such a process of extracting a network address or a process of performing a table retrieval to be performed after the extracting process has been a bottleneck in a relay process in an IP router.
Even utilization of a content addressable memory (CAM) for the purpose of simplifying the process has not been able to make the best use of its merit, since due to variation of the bit length of a mask, a CAM is required for each corresponding bit length.